import java.util.Arrays;



/*
 * @lc app=leetcode.cn id=912 lang=java
 *
 * [912] 排序数组
 */

// @lc code=start
class Solution {
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length < 2)
            return nums;
        
        SortMethod.heapSort(nums, 0, nums.length - 1);
        return nums;
    }

    static class SortMethod {

        // 插入排序第k次遍历都会维护前k个数有序，将k+1个数插入到正确的位置，重复这个过程
        static void insertionSort(int[] nums, int start, int end) {
            for (int i = start + 1; i <= end; i++) {
                int val = nums[i];
                int j = start;
                // 首先找到i之前第一个比nums[i]大的下标（或者没找到达到了j=i）
                while (nums[j] <= nums[i] && j < i)
                    j++;

                // 如果j移动到了i，那么说明第i个元素此时的位置是正确的，就不需处理
                // 否则需要把第i个数插入到j的位置上，并将之前的数往后移一位
                if (j != i) {
                    for (int k = i; k > j; k--) {
                        // 从后往前赋值不会产生错误
                        nums[k] = nums[k - 1];
                    }
                    nums[j] = val;
                }

            }
        }

        // 会超时
        static void bubbleSort(int[] nums, int start, int end) {

            for (int i = start; i < end; ++i) {
                // 设置后方的判断截止点
                for (int j = start; j < end - i + start; j++) {
                    if (nums[j] > nums[j + 1]) {
                        nums[j] = nums[j]^nums[j+1];
                        nums[j+1] = nums[j]^nums[j+1];
                        nums[j] = nums[j]^nums[j+1];
                    }

                }
                // System.out.println(Arrays.toString(nums));
            }
        }
        

        // 一般的快速排序,要注意1个关键的顺序
        static void quickSort(int[] nums, int start, int end){
            if(start>=end) return;
            int pivot = nums[end];
            int i = start,j = end;
            while(i<j){
                // 关键！！：在右侧取pivot时，指针遍历就要从左侧开始，反之亦然
                // 因为可以理解为取pivot处的值已经无用了（挖了一个坑），需要被其他值代替
                // pivot的值被记录了可以恢复，其他值不可以
                // 所以从反向遍历，第一个被替换的一定是pivot所处的位置，其可在最后被恢复
                // 但是如果遍历方向错了，第一个被覆盖的值必定不是pivot，而它就无法恢复了
                
                while(nums[i]<=pivot&&i<j) i++;
                if(i<j){
                    nums[j--] = nums[i];
                }
                while(nums[j]>=pivot&&i<j) j--;
                if(i<j){// 2个判断其实替代了swap
                    nums[i++] = nums[j];
                }
                
            }
            // 此时，ij必定重合，所以从此开始，ij可以互换
            nums[j] = pivot;
            quickSort(nums, start, i-1);
            quickSort(nums, i+1, end);
            
        }

        // 双轴快排，核心思想是定义两个pivot（直接取的话取最左和最右），将这两个pivot排好序
        // 比p1小的在左，比p2大的在右，在两者中间的位于中间
        // 这实际上是3路递归
        static void dualPivotSort(int[] nums, int start, int end){

        }
        
        /**
         * 维护最大堆而进行的堆排序
         * @param a 要排序的数组
         * @param low 最小下表，包含
         * @param high 最大下标，不包含
         */
        static void heapSort(int[] a, int low, int high) {
            // 此处(low + high)/2正好是这个完全二叉树中叶节点的个数（从low开始）
            // 这也就相当于用约前面一半的节点把后面剩下的（全部都在叶节点）都“清洗一遍”
            // 这样非叶节点在构建过程中始终保持着堆结构，而叶节点通过”清洗“，也维持了堆结构
            // 这样，只对堆数组的0~(low + high)/2进行percolateDown就可以使整个数组维持堆结构
            for (int k = (low+high)/2; k >= low; k--) {
                // 从后往前pushDown，这样可以减少交换循环的次数
                pushDown(a, k, a[k], low, high);
            }
            
            // 将前一半pushDown下去后，头部可以确保始终最大
            // 每次取处最大的节点从后往前放
            for (;high > low;--high) {
                int max = a[low];// 此时头部必然是最大的
                pushDown(a, low, a[high], low, high-1);
                a[high] = max;
                
            }
        }

    /**
     * 堆结构中的percolateDown方法，将特定元素在队中向下压，可以看出堆是最大堆
     *
     * @param a the given array
     * @param p the start index
     * @param value the given element
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, inclusive, to be sorted
     */
        private static void pushDown(int[] a, int p, int value, int low, int high) {
            // 可以看出heap结构是从0开始的
            // 注意这种赋值方法，可以利用for循环将变量限定在代码块中
            for (int k ;; a[p] = a[p = k]) {
                // 对于从0开始下的堆结构，左右子节点的index = father<<1+1和father<<1+2;
                // 在存在偏移的时候，要先×2再减去left
                k = (p << 1) - low + 2; // 计算右子节点的index
                // 先遍历右节点是有意义的，这样可以最大限度保证稳定性

                // 左节点也不在范围内
                if (k > high+1) {
                    break;
                }

                // 左节点在范围内但没有右节点，或者左节点比右节点要大，都把指针指向左节点
                if (k == high+1 || a[k] < a[k - 1]) {
                    --k;
                }

                // 当前指向的最大的节点也比value要小
                if (a[k] <= value) {
                    break;
                }
            }
            a[p] = value;
        }
    }

}
// @lc code=end

// 排序模式普遍是：数组，起始index，结尾index
